package DP;

/**
 * @author 曹见朋
 * @create 2024-06-12-23:57
 */
public class Main377 {
    // TODO 377. 组合总和 Ⅳ
    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        int len = nums.length;

        for(int j = 0; j <= target; j++){
            for(int i = 0; i < len; i++){
                if(j >= nums[i]){
                    dp[j] += dp[j - nums[i]];
                }else{
                    dp[j] = dp[j];
                }
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        int target = 4;

        int i = combinationSum4(nums, target);
        System.out.println(i);
    }
}
